Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 82/115

Q: Choose the correct properties of weak-heap.
A. Every node has value greater than the value of child node
B. Every right child of node has greater value than parent node
C. Every left child of node has greater value than parent node
D. Every left and right child of node has same value as parent node
Solution: This is the property of a weak heap.
Q: What is the other name of weak heap?
A. Min-heap
B. Max-heap
C. Relaxed -heap
D. Leonardo heap
Solution: Relaxed heap is just another name of weak heap.
Q: What is the worst case time in searching minimum value in weak -heap?
A. O(log n)
B. O(n)
C. O(n logn)
D. O(1)
Solution: Weak heap is an array based form that supports the operation of finding a minimum in O(1).
Q: The total comparisons in finding both smallest and largest elements are
A. 2*n +2
B. n + ((n+1)/2) -2
C. n+logn
D. n2 
Solution: The total comparisons in finding smallest and largest elements is n + ((n+1)/2) – 2.
Q: What is the complexity of given function of insertion.

	insert(int n)
	{
		if(buffer_size()< maxi_biffer_size())
		buffer_aar[ind]==n;
		else
		move_to_heap(buffer,buffer+maxi_buffer_size())
	}
A. O(logn)
B. amortized O(1)
C. O(n)
D. O (n*logn)
Solution: Use a buffer array to store a fixed number of elements when the buffer is full the content of buffer is moved to heap.As a result the complexity
is amotized O(1).
Q: The leaf node for a heap of height h will be at which position.
A. h
B. h-1
C. h or h-1
D. h-2
Solution: A complete binary tree is also a heap so by the property of binary tree the leaf nodes will be must at height h or h-1.
Q: The main distinguishable characterstic of a binomial heap from a binary heap is that
A. it allows union operations very efficiently
B. it does not allow union operations that could easily be implemented in binary heap
C. the heap structure is not similar to complete binary tree
D. the location of child node is not fixed i.e child nodes could be at level (h-2) or (h-3), where h is height of heap and h>4
Solution: The main use of binomial heap is to unify two different heap efficiently.
Q: The number of trees in a binomial heap with n nodes is
A. logn
B. n
C. nlogn
D. n/2
Solution: At each depth there is a binomial tree in a binomial heap.
Q: In a binomial heap the root value is greater than left child and less than right child.
A. True
B. False
C. none
D. ...
Solution: Binomial tree used in making binomial heap follows min heap property.
Q: Given the pseudo code, state whether the function for merging of two heap is correct or not?

		mergeTree(p,q)
    		if p.root.value <= q.root.value
        	return p.addTree(q)
    		else
        	return q.addTree(p)
A. True
B. False
C. none
D. ...
Solution: Binomial heap has a property that root value is less than both the child node’s value. So the given function of merging two different heap is correct.

You Have Score    /10